<HTML>
<HEAD>
<!-- This HTML file has been created by texi2html 1.29
     from typetutorial.tnf on 19 December 2010 -->

<TITLE>Tutorial on Type Analysis - Union Types</TITLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000EE" VLINK="#551A8B" ALINK="#FF0000" BACKGROUND="gifs/bg.gif">
<TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0" VALIGN=BOTTOM>
<TR VALIGN=BOTTOM>
<TD WIDTH="160" VALIGN=BOTTOM>
<A HREF="http://eli-project.sourceforge.net/">
<IMG SRC="gifs/elilogo.gif" BORDER=0>
</A>&nbsp;
</TD>
<TD WIDTH="25" VALIGN=BOTTOM>
<img src="gifs/empty.gif" WIDTH=25 HEIGHT=25>
</TD>
<TD ALIGN=LEFT WIDTH="475" VALIGN=BOTTOM>
<A HREF="index.html"><IMG SRC="gifs/title.png" BORDER=0></A>
</TD>
<!-- |DELETE FOR SOURCEFORGE LOGO|
<TD>
<a href="http://sourceforge.net/projects/eli-project">
<img
  src="http://sflogo.sourceforge.net/sflogo.php?group_id=70447&amp;type=13"
  width="120" height="30"
  alt="Get Eli: Translator Construction Made Easy at SourceForge.net.
    Fast, secure and Free Open Source software downloads"/>
</a>
</TD>
|DELETE FOR SOURCEFORGE LOGO| -->
</TR>
</TABLE>

<HR size=1 noshade width=785 align=left>
<TABLE BORDER=0 CELLSPACING=2 CELLPADDING=0>
<TR>
<TD VALIGN=TOP WIDTH="160">
<h4>General Information</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="index.html">Eli: Translator Construction Made Easy</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="gindex_1.html#SEC1">Global Index</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="faq_toc.html" >Frequently Asked Questions</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Tutorials</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="EliRefCard_toc.html">Quick Reference Card</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="novice_toc.html">Guide For new Eli Users</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="news_toc.html">Release Notes of Eli</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="nametutorial_toc.html">Tutorial on Name Analysis</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="typetutorial_toc.html">Tutorial on Type Analysis</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Reference Manuals</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ui_toc.html">User Interface</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="pp_toc.html">Eli products and parameters</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lidoref_toc.html">LIDO Reference Manual</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Libraries</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lib_toc.html">Eli library routines</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="modlib_toc.html">Specification Module Library</a></td></tr>
</table>

<h4>Translation Tasks</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lex_toc.html">Lexical analysis specification</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="syntax_toc.html">Syntactic Analysis Manual</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="comptrees_toc.html">Computation in Trees</a></td></tr>
</table>

<h4>Tools</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lcl_toc.html">LIGA Control Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="show_toc.html">Debugging Information for LIDO</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="gorto_toc.html">Graphical ORder TOol</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="fw_toc.html">FunnelWeb User's Manual</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ptg_toc.html">Pattern-based Text Generator</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="deftbl_toc.html">Property Definition Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="oil_toc.html">Operator Identification Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="tp_toc.html">Tree Grammar Specification Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="clp_toc.html">Command Line Processing</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="cola_toc.html">COLA Options Reference Manual</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="idem_toc.html">Generating Unparsing Code</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="mon_toc.html">Monitoring a Processor's Execution</a> </td></tr>
</table>

<h4>Administration</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="sysadmin_toc.html">System Administration Guide</a> </td></tr>
</table>

<HR WIDTH="100%">
<A HREF="mailto:eli-project-users@lists.sourceforge.net">
<IMG SRC="gifs/button_mail.gif" BORDER=0 ALIGN="left"></A>
<A HREF="index.html"><IMG SRC="gifs/home.gif" BORDER=0 ALIGN="right"></A>

</TD>
<TD VALIGN=TOP WIDTH="25"><img src="gifs/empty.gif" WIDTH=25 HEIGHT=25></TD>

<TD VALIGN=TOP WIDTH="600">
<H1>Tutorial on Type Analysis</H1>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="typetutorial_6.html"><IMG SRC="gifs/prev.gif" ALT="Previous Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="typetutorial_8.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="typetutorial_toc.html"><IMG SRC="gifs/up.gif" ALT="Table of Contents" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT="">
<HR size=1 noshade width=600 align=left>
<H1><A NAME="SEC11" HREF="typetutorial_toc.html#SEC11">Union Types</A></H1>
<P>
We introduce union types to our language in order to
demonstrate how subtype relations and their coercions are specified.
A union type is described by a sequence of type denotations, which
constitute the subtypes of the specified union type.
A value of one of the subtypes can be coerced to the union type.
A value of a union type can be treated as a value of one of
the subtypes using a cast operation or a case statement.
<P>
Here is an example program that defines and uses a union
variable named <CODE>rv</CODE>:
<P>
<B>UnionExamp</B>[75]==
<PRE>
begin
  var   union int, bool end rv;
  var   int j, bool c;
  rv = 42; rv = true;
  j = &#60;int&#62; rv;
  case rv of
    int t: j = t;
    bool t: c = t;
  end
end
</PRE>
<PRE>
This macro is attached to a product file.
</PRE>
<P>
In the <CODE>case</CODE> statement the <CODE>case</CODE> expression has a union
type. Each case declares a variable of a subtype of that
union type. The branch which corresponds to the current type 
of the <CODE>case</CODE> expression is selected, its variable is
initialized with the value of the <CODE>case</CODE> expression,
and the statement is executed.
<P>
The following productions describe union types, type casts,
and <CODE>case</CODE> statements:
<I>Abstract union syntax</I>[76]==
<PRE>
RULE: TypeDenoter ::= UnionType END;
RULE: UnionType  ::= 'union' UnitedTypes 'end' END;
RULE: UnitedTypes LISTOF UnitedType END;
RULE: UnitedType ::= TypeDenoter END;

RULE: Expression ::= '&#60;' TypeDenoter '&#62;' Expression END;

RULE: Statement ::= CaseStmt END;
RULE: CaseStmt ::= 'case' Expression 'of' Cases 'end' END;
RULE: Cases LISTOF Case END;
RULE: Case ::= ObjDecl ':' Statement END;
</PRE>
<PRE>
This macro is invoked in definition 88.
</PRE>
<P>
The following computations introduce a type denoter for union types
and associate properties for test output to it:
In order to check whether a type is a union type, as required
for example in a case statement, we introduce a property
<CODE>IsUnionType</CODE>. 
<I>Is union type</I>[77]==
<PRE>
IsUnionType: int;
</PRE>
<PRE>
This macro is invoked in definition 87.
</PRE>
<P>
<I>Union type denoter</I>[78]==
<PRE>
SYMBOL UnionType INHERITS TypeDenotation END;

RULE: UnionType ::= 'union' UnitedTypes 'end' COMPUTE
  .GotTypeProp =
      ORDER (
        ResetIsUnionType (UnionType.Type, 1),
        ResetTypeName (UnionType.Type, "union..."),
        ResetTypeLine (UnionType.Type, LINE));
END;

RULE: TypeDenoter ::= UnionType COMPUTE
  TypeDenoter.Type = UnionType.Type;
END;
</PRE>
<PRE>
This macro is invoked in definition 88.
</PRE>
<P>
For the comparison of union types stuctural equivalence is
specified, such that the fact that it is a union type and
the sequence of subtypes are relevant for type equality. 
<CODE>UnionClass</CODE> is the the set 
containing all union types for initialization of the 
equivalence check.
<P>
<I>Union type class</I>[79]==
<PRE>
UnionClass;
</PRE>
<PRE>
This macro is invoked in definition 87.
</PRE>
<P>
The <CODE>UnionClass</CODE> and the sequence <CODE>UnitedTypes.OpndTypeList</CODE>
are used as arguments of <CODE>AddTypeToBlock</CODE> to specify type
equivalence of union types. Property <CODE>ComponentTypes</CODE> is
set accordingly:
<P>
<I>Union type equality computation</I>[80]==
<PRE>
RULE: UnionType ::= 'union' UnitedTypes 'end' COMPUTE
  UnionType.GotType =
      AddTypeToBlock 
        (UnionType.Type, UnionClass, 
         VResetComponentTypes (UnionType.Type, UnitedTypes.OpndTypeList))
      &#60;- .GotTypeProp;
END;

SYMBOL UnitedTypes INHERITS OpndTypeListRoot END;
SYMBOL UnitedType  INHERITS OpndTypeListElem END;

RULE: UnitedType ::= TypeDenoter COMPUTE
  UnitedType.Type = TypeDenoter.Type;
  UnitedType.DefTableKeyElem = UnitedType.Type;
END;
</PRE>
<PRE>
This macro is invoked in definition 88.
</PRE>
<P>
Note, that here the order of the subtypes in the type denoter
is relevant for type equality. If that is not desired,
one could for example sort the list of the component types
in a canonical order before using it as an argument of
<CODE>AddTypeToBlock</CODE>.
<P>
For each union type we introduce two groups of conversion 
operators: A widening coercion from each subtype type to the 
union type, and a down cast from the union type to each subtype.
For the latter an indication has to be introduced:
<I>Downcast indication</I>[81]==
<PRE>
DownCast;
UnionWiden;
</PRE>
<PRE>
This macro is invoked in definition 87.
</PRE>
<P>
As a pair of operators has to be introduced for each subtype,
the context of the subtype denoter is the right place
to do it.
The coercion operator is not created explicitly; 
it is only stated that the subtype is <CODE>Coercible</CODE> to
the union type. The down cast conversion is introduced
as a <CODE>MonadicOperator</CODE>:
<P>
<I>Widening coercion computation</I>[82]==
<PRE>
SYMBOL UnitedType INHERITS OperatorDefs COMPUTE
  SYNT.GotOper =
    ORDER
      (Coercible (UnionWiden, THIS.Type, INCLUDING UnionType.Type),
       MonadicOperator
        (DownCast, NewKey(), 
         INCLUDING UnionType.Type, THIS.Type));
END;
</PRE>
<PRE>
This macro is invoked in definition 88.
</PRE>
<P>
The context of the down cast construct connects two expression
trees: The left-hand side of the rule is a leaf of the upper
expression tree. Its Type is stated to be the target type of the
cast. 
<P>
The casted expression is a root of an expression tree,
which is required to be converted to target type of the cast,
where all conversion operators of the <CODE>DownCast</CODE> indication
may be applied additionally to the coercions:
<P>
<I>Down cast</I>[83]==
<PRE>
RULE: Expression ::= '&#60;' TypeDenoter '&#62;' Expression COMPUTE
  PrimaryContext (Expression[1], TypeDenoter.Type);

  RootContext (TypeDenoter.Type, , Expression[2]);
  Indication (DownCast);
END;
</PRE>
<PRE>
This macro is invoked in definition 88.
</PRE>
<P>
In a <CODE>case</CODE> statement it is required that the <CODE>case</CODE>
expression has a union type:
<P>
<I>Union case statement</I>[84]==
<PRE>
SYMBOL CaseStmt: Type: DefTableKey;

RULE: CaseStmt ::= 'case' Expression 'of' Cases 'end' COMPUTE
  CaseStmt.Type = Expression.Type;

  IF (NOT (GetIsUnionType (Expression.Type, 0)),
  message (ERROR, "Case expression must have a union type",
           0,COORDREF))
  &#60;- INCLUDING Program.TypeIsSet;
END;
</PRE>
<PRE>
This macro is invoked in definition 88.
</PRE>
<P>
Each branch of a <CODE>case</CODE> statement forms a range for
the declaration of the variable that gets the value of the
<CODE>case</CODE> expression if that case is selected.
It is required that the type of the variable is a subtype of
the type of the case expression.
We here require that it is coercible to the type of the
<CODE>case</CODE> expression, although that is not quite exact.
<I>Union case</I>[85]==
<PRE>
SYMBOL Case INHERITS RangeScope END;

RULE: Case ::= ObjDecl ':' Statement COMPUTE
  IF (NOT (IsCoercible 
             (ObjDecl.Type, INCLUDING CaseStmt.Type)),
  message (ERROR, "Must be a subtype of the case expression",
           0, COORDREF))
  &#60;- INCLUDING Program.GotType;
END;
</PRE>
<PRE>
This macro is invoked in definition 88.
</PRE>
<P>
In other contexts <CODE>ObjDecl</CODE> occurs in a CHAIN.
To avoid an error message on missing a chain start we apply the 
role <CODE>OpndTypeListRoot</CODE> here, which has the CHAINSTART, although
that role is not needed:
<P>
<I>Union CHAIN workaraound</I>[86]==
<PRE>
SYMBOL Cases INHERITS OpndTypeListRoot END;
</PRE>
<PRE>
This macro is invoked in definition 88.
</PRE>
<P>
<B>Union.pdl</B>[87]==
<PRE>
<I>Is union type</I>[77]
<I>Union type class</I>[79]
<I>Downcast indication</I>[81]
</PRE>
<PRE>
This macro is attached to a product file.
</PRE>
<P>
<B>Union.lido</B>[88]==
<PRE>
<I>Abstract union syntax</I>[76]
<I>Union type denoter</I>[78]
<I>Union type equality computation</I>[80]
<I>Widening coercion computation</I>[82]
<I>Down cast</I>[83]
<I>Union case</I>[85]
<I>Union case statement</I>[84]
<I>Union CHAIN workaraound</I>[86]
</PRE>
<PRE>
This macro is attached to a product file.
</PRE>
<P>
<B>Union.con</B>[89]==
<PRE>
<I>Concrete union syntax</I>[144]
</PRE>
<PRE>
This macro is attached to a product file.
</PRE>
<P>
<HR size=1 noshade width=600 align=left>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="typetutorial_6.html"><IMG SRC="gifs/prev.gif" ALT="Previous Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="typetutorial_8.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="typetutorial_toc.html"><IMG SRC="gifs/up.gif" ALT="Table of Contents" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT="">
<HR size=1 noshade width=600 align=left>
</TD>
</TR>
</TABLE>

</BODY></HTML>
